package exercises.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/set-matrix-zeroes/">
 * 73. 矩阵置零</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 * <p>
 * 进阶：
 * <p>
 * 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * <p>
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * <p>
 * 你能想出一个仅使用常量空间的解决方案吗？
 *
 * @author or2
 * @date 2021年09月24日 时间: 10:46
 */
public class No73 {
    public void setZeroes(int[][] matrix) {
        int rowLength = matrix[0].length;
        /*记录第一列信息*/
        boolean firstRow = false;
        for (int[] col : matrix) {
            if (col[0] == 0) {
                firstRow = true;
            }

            /*标记需要清空的行和列*/
            for (int i = 1; i < rowLength; i++) {
                if (col[i] == 0) {
                    matrix[0][i] = 0;
                    col[0] = 0;
                }
            }
        }

        /*根据列信息清理列*/
        for (int i = 1; i < rowLength; i++) {
            if (matrix[0][i] == 0) {
                for (int[] col : matrix) {
                    col[i] = 0;
                }
            }
        }
        /*根据行信息清理行*/
        for (int[] col : matrix) {
            if (col[0] == 0) {
                Arrays.fill(col, 0);
            }
        }
        /*第一列处理*/
        if (firstRow) {
            for (int[] col : matrix) {
                col[0] = 0;
            }
        }
    }
}
